#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:

    """
    默认nums是排序过得
    """

    def permuteUnique(self, nums):
        # nums.sort()
        self.ret = []
        self.rec_permute(nums, [])
        return self.ret

    def rec_permute(self, nums, path):
        # 效率并不算太好: 因为大量copy nums, path, pop
        if not nums:
            self.ret.append(path)
            return

        l = len(nums)

        processed_set = set()
        for i,v  in enumerate(nums):
            # 判断元素是否处理过: 如果处理过, 表示是相同元素, 则略过. 相当于截枝.
            if v in processed_set:
                continue
            processed_set.add(v)

            # 判断元素是否处理过: 如果处理过, 表示是相同元素, 则略过. 相当于截枝.
            # 如果元素是排序过的, 可以用这种方式判断是否处理过: 否则使用set判断
            # if i != 0 and v == nums[i-1]:
            #     continue

            # copy
            new_nums = list(nums)
            new_path = list(path)

            # drive rec
            new_nums.pop(i)
            new_path.append(v)
            self.rec_permute(new_nums, new_path)


def main():
    print("start main")
    s = Solution()
    # ret = s.permuteUnique([1,2,2])
    ret = s.permuteUnique([3, 3, 0, 3])
    print(ret)

if __name__ == "__main__":
    main()
